package dfs;

class ListNode{
    ListNode next;
    int val;
}

public class Demo2 {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        return merg(list1,list2);
    }
    public ListNode merg(ListNode list1,ListNode list2){
        if(list1==null)return list2;
        if(list2==null)return list1;
        if(list1.val<list2.val){
            ListNode cur=list1.next;
            list1.next=merg(cur,list2);
            return list1;
        }else{
            ListNode cur=list2.next;
            list2.next=merg(cur,list1);
            return list2;
        }
    }
}
